9591. Лексикография
Люси любит буквы. Она
изучала определение лексикографического порядка в школе и играет с ним.
Сначала она попыталась
составить лексикографически наименьшее слово из заданных букв. Это было так
просто! Затем она попыталась составить несколько слов и свести к минимуму одно
из них. Это было намного сложнее!
Формально Люси
хочет составить n слов длины l каждое из заданных n * l букв, чтобы k-ое из них в
лексикографическом порядке было лексикографически наименьшим.
Вход. Первая строка
содержит три целых числа n, l и k (1 ≤ k ≤ n ≤ 1000, 1 ≤
l ≤ 1000) – общее
количество слов, длина каждого слова и индекс слова, которое Люси хочет
минимизировать.
Далее следует
строка из n * l строчных букв
английского алфавита.
Выход. Выведите n слов по l букв каждое, по
одному слову в строке, используя буквы из входных данных. Слова должны быть
отсортированы в лексикографическом порядке, а k - ое из них
должно быть лексикографически как можно меньше. Если существует несколько ответов с
наименьшим k-ым словом, то выведите любой из них.
|
Пример
входа 1 |
Пример
выхода 1 |
|
3
2 2 abcdef |
ad bc ef |
|
|
|
|
Пример
входа 2 |
Пример
выхода 2 |
|
2
3 1 abcabc |
aab bcc |
РЕШЕНИЕ
жадность
Анализ алгоритма
Отсортируем
заданные буквы. Пусть v – результирующий двумерный символьный
массив. Будем заполнять его по столбцам: сначала заполняем буквами первый
столбец, потом второй и так далее. Сначала столбцы заполняем до k-ой строки.
После того как розданы буквы в первом столбце (от 1 до k-ой строки), нам следует найти минимальный номер строки pt, совпадающей с k-ой. Раздаем буквы во втором столбце от строки pt до k-ой. Снова ищем минимальный номер строки pt, совпадающей с k-ой. Раздаем буквы в третьем столбце от строки pt до k-ой. И так далее пока вся k-ая строка не будет заполнена.
Оставшиеся буквы раздаем произвольным образом, k-ое слово в любом случае будет
лексикографически наименьшим. Например, можно раздать оставшиеся буквы в лексикографическом
порядке по строкам сверху вниз и слева направо.
Пример
Рассмотрим следующий тест
6 3 6
fgahhfgaaebdcbbebc
Отсортируем строку: aaabbbbccdeeffgghh. Нам следуем заполнить матрицу из 6 слов по 3 буквы, минимизировав при
этом 6-е слово.
Заполняем первый столбец буквами сверху вниз (от 1-го до 6-го слова). Второй
столбец следует заполнять буквами, начиная с самой ранней строки, у которой префикс
совпадает с 6-ой. Положим pt = 4, и
заполняем буквами второй столбец от строки номер pt до 6-ой. Наименьшей строкой,
префикс которой совпадает с 6-ой, будет строка pt = 5. Начинаем с этой строки раздавать третью букву вплоть до 6-ой строки.
Строка номер 6 при такой раздаче букв оказалась минимальной.
Далее раздаем недостающие буквы в лексикографическом порядке. Например, это
можно сделать по строкам сверху вниз и слева направо.
Рассмотрим первый тест
3 2 2
abcdef
Отсортируем строку: abcdef. Нам следуем заполнить матрицу из 3 слов по 2 буквы, минимизировав при
этом 2-е слово.
Заполняем первый столбец буквами сверху вниз (от 1-го до 2-го слова). Второй столбец следует заполнять буквами, начиная с самой
ранней строки, у которой префикс совпадает с 2-ой. Положим pt = 2, и заполняем буквами второй столбец от строки номер pt до 2-ой. Строка номер 2 при такой раздаче букв оказалась минимальной.
Далее раздаем недостающие буквы в лексикографическом порядке по строкам сверху вниз и слева направо.
Реализация алгоритма
cin >> n >> l >> k;
cin >> s;
Отсортируем
буквы во входной строке. Текущей обрабатываемой буквой будет s[pos].
pos = 0;
sort(s.begin(), s.end());
Объявим
выводимую матрицу букв v (n слов по l букв).
vector<string> v(n, string(l, ' '));
Раздаем буквы по
столбцу номер j по строкам от pt до k – 1 (нумерация строк идет с нуля).
int pt = 0;
for (j = 0; j < l; j++)
{
for (i = pt; i <
k; i++)
v[i][j] = s[pos++];
Двигаем pt вперед (pt++) пока j-ый символ (k – 1)-ой строки не будет совпадать с j-ым символом строки pt. pt указывает на строку с наименьшим номером, которая на данный момент совпадает
с (k – 1)-ой.
while (v[pt][j] != v[k - 1][j]) pt++;
}
Заполняем
остальные буквы матрицы. Двигаемся по строкам
сверху вниз и слева направо.
for (i = 0; i < n; i++)
for (j = 0; j < l; j++)
if (v[i][j] == ' ') v[i][j] = s[pos++];
Выводим ответ.
for (i = 0; i < n; i++)
cout << v[i] << endl;